///\todo upgrade

//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2011 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_CONTAINER_CRANGESET_H_
#define _BUOLA_CONTAINER_CRANGESET_H_

#include <buola/buola.h>

namespace buola {

///\addtogroup container
///@{

/////////////////////////////////////////////////////////////////////////////////////////////////

/// range-based set

/// Set of objects of some integral type where the presence of each element is stored as ranges
/// of consecutive numbers. For this reason, it is most efficient when the members of the set
/// appear in groups of consecutive numbers.
///
/// It provides an interface which is suitable for use for the implementation of \ref CCharSet.
///
/// \tparam tChar the integral type.
///
/////////////////////////////////////////////////////////////////////////////////////////////////
    
template<typename tChar>
class CRangeSet
{
    /// range
    struct SRange
    {
        /// default constructor
        SRange()
            :   mFirst()
            ,   mLast()
        {}
        
        /// initializes the range
        SRange(tChar pFirst,tChar pLast)
            :   mFirst(pFirst)
            ,   mLast(pLast)
        {}
        
        /// returns \c true if the range contains the character
        bool Contains(tChar pC) const
        {
            return mFirst<=pC&&pC<=mLast;
        }
        
        /// returns \c true if the range totally contains the other range
        bool Contains(const SRange &pO) const
        {
            return mFirst<=pO.mFirst&&pO.mLast<=mLast;
        }
        
        /// returns \c true if the two ranges can be merged
        
        /// Two ranges can be merged if they overlap or are adjacent
        bool CanMerge(const SRange &pO) const
        {
            typedef std::numeric_limits<tChar> tTraits;
            
            tChar lFirstm1=mFirst==tTraits::min()?mFirst:mFirst-1;
            tChar lLastp1=mLast==tTraits::max()?mLast:mLast+1;

            return lFirstm1<=pO.mLast&&lLastp1>=pO.mFirst;
        }
        
        /// merges the range \p pO into this range
        
        /// The function assumes that the ranges can be first
        void Merge(const SRange &pO)
        {
            mFirst=std::min(mFirst,pO.mFirst);
            mLast=std::max(mLast,pO.mLast);
        }
        
        /// returns \c true if the character is less than any character in this range
        friend bool operator<(tChar pChar,const SRange &pRange)
        {
            return pChar<pRange.mFirst;
        }

        /// returns \c true if the range \p pLH starts before this range
        friend bool operator<(const SRange &pLH,const SRange &pRH)
        {
            return pLH.mFirst<pRH.mFirst;
        }
        
        /// returns \c true if the character is more than the first character in this range
        friend bool operator<(const SRange &pRange,tChar pChar)
        {
            return pRange.mFirst<pChar;
        }
        
        tChar mFirst,mLast;
    };

    typedef std::vector<SRange> tStorage;

public:
    /// default constructor 
    CRangeSet()
    {}
    
    /// copy constructor
    CRangeSet(const CRangeSet &pRH)
        :   mSet(pRH.mSet)
    {}
    
    /// move constructor
    CRangeSet(CRangeSet &&pRH)
        :   mSet(std::move(pRH.mSet))
    {}
    
private:
    /// tries to merge the range \p pRange into the range pointed to by \p pI
    bool TryMerge(typename tStorage::iterator pI,const SRange &pRange)
    {
        if(!pI->CanMerge(pRange)) return false;

        pI->Merge(pRange);
        
        typename tStorage::iterator lI=pI+1;
        
        //skip subsequent ranges totally included in *pI
        while(lI!=mSet.end()&&lI->mLast<=pI->mLast) ++lI;
        //collapse the next one if it overlaps
        if(lI!=mSet.end()&&pI->mLast+1>=lI->mFirst)
        {
            pI->mLast=lI->mLast;
            ++lI;
        }
        //erase skipped ones
        mSet.erase(pI+1,lI);
            
        return true;
    }

public:
    /// tests if a character \p pC is part of the set
    bool Test(tChar pC) const
    {
        auto i=std::upper_bound(mSet.begin(),mSet.end(),pC);
        
        if(i==mSet.begin()) return false;
        
        return (--i)->Contains(pC);
    }
    
    /// adds the character \p pC to the set
    void Add(tChar pChar)
    {
        Add(pChar,pChar);
    }

    /// adds the range [\p pFirst,\p pLast] to the set
    void Add(tChar pFirst,tChar pLast)
    {
        if(pLast<pFirst) return;
        
        SRange lRange(pFirst,pLast);
        
        if(mSet.empty())
        {
            mSet.push_back(lRange);
            return;
        }
        
        auto i=std::upper_bound(mSet.begin(),mSet.end(),lRange);
        
        if(i!=mSet.begin())
        {
            if((i-1)->Contains(lRange))
                return;
            
            if(TryMerge(i-1,lRange))
                return;
        }
        
        if(i==mSet.end()||!TryMerge(i,lRange))
        {
            mSet.insert(i,lRange);
        }
    }
    
    /// adds the set \p pSet to this set
    void Add(const CRangeSet &pSet)
    {
        for(auto i=pSet.mSet.begin();i!=pSet.mSet.end();++i)
        {
            Add(i->mFirst,i->mSecond);
        }
    }

    /// removes the character \p pC from the set
    void Remove(tChar pChar)
    {
        Remove(pChar,pChar);
    }

    /// removes the range [\p pFirst,\p pLast] from the set
    void Remove(tChar pFirst,tChar pLast)
    {
        if(mSet.empty())
            return;
        
        if(pLast<pFirst) return;
        
        SRange lRange(pFirst,pLast);
        
        auto i=std::upper_bound(mSet.begin(),mSet.end(),lRange);

        if(i!=mSet.begin())
        {
            auto l=i-1;
        
            if(l->mFirst<lRange.mFirst)
            {
                if(l->mLast>lRange.mLast)
                {
                    //it is completely inside
                    tChar lLast=l->mLast;
                    l->mLast=lRange.mFirst-1;
                    mSet.insert(i,SRange(lRange.mLast+1,lLast));
                    return;
                }
                else if(l->mLast>=lRange.mFirst)
                {
                    l->mLast=lRange.mFirst-1;
                }
            }
            else
            {
                //they start at the same point, it will be removed or truncated
                i=l;
            }
        }
        
        auto r=i;
        
        //skip ranges included in lRange
        while(r!=mSet.end()&&r->mLast<=lRange.mLast) ++r;

        if(r!=mSet.end()&&lRange.mLast>=r->mFirst)
            r->mFirst=lRange.mLast+1;
        
        mSet.erase(i,r);
    }

    /// removes the set \p pSet from this set
    void Remove(const CRangeSet &pSet)
    {
        for(auto i=pSet.mSet.begin();i!=pSet.mSet.end();++i)
        {
            Remove(i->mFirst,i->mSecond);
        }
    }

    /// inverts the set
    void Invert()
    {
        typedef std::numeric_limits<tChar> tTraits;

        tChar lMin=tTraits::min();
        tChar lMax=tTraits::max();
        
        if(mSet.empty())
        {
            mSet.push_back(SRange(lMin,lMax));
            return;
        }
        
        if(mSet.front().mFirst==lMin)
        {
            if(mSet.front().mLast==lMax)
            {
                mSet.clear();
                return;
            }

            lMin=mSet.front().mLast+1;
            mSet.erase(mSet.begin());
        }
        
        for(auto i=mSet.begin();i!=mSet.end();++i)
        {
            tChar lLast=i->mLast;
            i->mLast=i->mFirst-1;
            i->mFirst=lMin;
            if(lLast==lMax) return;
            lMin=lLast+1;
        }
        
        mSet.push_back(SRange(lMin,lMax));
    }
    
    /// sets this set to be the intersection of itself with \p pSet
    void Intersect(const CRangeSet &pSet)
    {
        CRangeSet lSet(pSet);
        lSet.Invert();
        Remove(lSet);
    }

    /// toggles all elements present in \p pSet
    void Xor(const CRangeSet &pSet)
    {
        CRangeSet lSet(*this);
        Add(pSet);
        lSet.Intersect(pSet);
        Remove(lSet);
    }

    /// removes all elements from the set
    void clear()
    {
        mSet.clear();
    }

    /// copy constructor
    CRangeSet &operator=(const CRangeSet &)=default;
    
    /// move constructor
    CRangeSet &operator=(CRangeSet &&pRH)
    {
        mSet=std::move(pRH.mSet);
    }

private:
    tStorage mSet;
};

///@}

/*namespace buola*/ }

#endif
